package qsc.algorithm.dijkstra;

import java.util.Arrays;

/**
 * @auther QiuShangcheng
 * @create 2021/4/23
 */
public class Dijkstra {
    private static final int N = 65535;//极大值,代表不可达

    /**
     * 迪杰斯特拉算法实现 参考博客：https://www.cnblogs.com/skywang12345/p/3711516.html
     *
     * (1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
     *
     * (2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
     *
     * (3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
     *
     * (4) 重复步骤(2)和(3)，直到遍历完所有顶点。
     *
     * @param vs 中心节点
     */
    public static void dijkstra(int vs, Graph graph) {
        //存储已经经过的节点
        boolean[] visited = new boolean[graph.getVertex().length];
        //前置节点
        int[] prev = new int[graph.getVertex().length];
        //储存中心节点到节点i的距离
        int[] dist = new int[graph.getVertex().length];
        Arrays.fill(dist, N);
        //初始化中心节点
        for (int i = 0; i < graph.getVertex().length; i++) {
            dist[i] = graph.getMatrix()[vs][i];
        }
        dist[vs] = 0;
        prev[vs] = vs;
        visited[vs] = true;

        //储存每次最小路径索引的临时变量
        int temp = vs;
        for (int i = 0; i < graph.getVertex().length; i++) {
            //寻找当前最小路径
            int min = N;
            for (int j = 0; j < graph.getVertex().length; j++) {
                if (visited[j] == false && dist[j] < min) {
                    min = dist[j];
                    temp = j;
                }
            }
            //标记为已访问
            visited[temp] = true;

            // 修正当前最短路径和前驱顶点
            // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
            for (int j = 0; j < graph.getVertex().length; j++) {
                //更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离
                int tep = graph.getMatrix()[temp][j] == N ? N : min + graph.getMatrix()[temp][j];
                if (visited[j] == false && tep < dist[j]) {
                    dist[j] = tep;
                    prev[j] = temp;
                }
            }

        }

        // 打印dijkstra最短路径的结果
        System.out.println("dist[]: "+Arrays.toString(dist));
        for (int j = 0; j < graph.getVertex().length; j++) {
            System.out.println("prev:"+prev[j]);
            System.out.printf("dijkstra(%c): ", graph.getVertex()[j]);
            System.out.printf("  shortest(%c, %c)=%d\n", graph.getVertex()[vs], graph.getVertex()[j], dist[j]);
        }
    }
}
